package com.LeeCode;

/**
 * 制作 m 束花所需的最少天数
 */

public class Code1482 {
    public static void main(String[] args) {
        int[] bloomDay = {1000000000, 1000000000};
        int m = 1, k = 1;
        System.out.println(new Code1482().minDays(bloomDay, m, k));
    }

    public int minDays(int[] bloomDay, int m, int k) {
        int left = 0, up = 0;
        for (int num : bloomDay) {
            up = Math.max(up, num + 1);
        }
        int right = up;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(bloomDay, m, k, mid))
                right = mid;
            else
                left = mid;
        }
        return right == up ? -1 : right;
    }

    private boolean check(int[] bloomDay, int m, int k, int day) {

        int canMake = 0, sum = 0;
        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= day) {
                if (i != 0 && bloomDay[i - 1] > day) {
                    sum = 0;
                }
                sum++;
            }
            if (sum == k) {
                canMake++;
                sum = 0;
            }
            if (canMake >= m)
                return true;
        }

        return false;
    }
}
